Definition

Define language L′L' as 𝐍𝐏\mathbf{NP}-complete if L′L' is NP-hard and L′∈L' \in NP.

(see NP, NP-hard)

Notes

  • if P≠NP, then by Ladner's theorem there exists problems which are 𝐍𝐏\mathbf{NP}-intermediate (NPI), i.e. between NP and NPC in complexity
    • else (if P=NP), then P = NP = NPC
  • intuition: if a problem X is in NPC, every problem Y in NP may be reduced to it, thus solving X efficiently means solving NP efficiently; similarly, every problem in NPC may be reduced to one in NP hard

References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 42.
  2. https://webdocs.cs.ualberta.ca/~zacharyf/courses/complexity_2019/notes/complexity-w19-lec04.pdf
  3. https://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf
  4. https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard